Section: New Results

Solving Systems over the Reals and Applications

Exact algorithms for linear matrix inequalities

Let $A\left(x\right)=A_0+x_1{A}_1+...+x_n{A}_n$ be a linear matrix, or pencil, generated by given symmetric matrices $A_0,A_1,...,A_n$ of size $m$ with rational entries. The set of real vectors $x$ such that the pencil is positive semidefinite is a convex semi-algebraic set called spectrahedron, described by a linear matrix inequality (LMI). In [13], we design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree $d$ of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear Bézout bound of $d$. When $m$ (resp. $n$) is fixed, such a bound, and hence the complexity, is polynomial in $n$ (resp. $m$). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms.

Real root finding for determinants of linear matrices

Let $A_0,A_1,...,A_n$ be given square matrices of size $m$ with rational coefficients. In [14], we focus on the exact computation of one point in each connected component of the real determinantal variety $\{x\in {ℝ}^n:det(A_0+x_1{A}_1+\cdots +x_n{A}_n)=0\}$. Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Using standard complexity results this problem can be solved using $m^{O\left(n\right)}$ arithmetic operations. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially quadratic in ${\left(\genfrac{}{}{0pt}{}{n+m}{n}\right)}^3$ . We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where $m$ is fixed, the complexity is polynomial in $n$.

A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets

A roadmap for a semi-algebraic set $S$ is a curve which has a non-empty and connected intersection with all connected components of $S$. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in higher-level algorithms. In [15], we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets. Its output size and running time are polynomial in ${\left(nD\right)}^{nlog\left(d\right)}$ , where $D$ is the maximum of the degrees of the input polynomials, $d$ is the dimension of the set under consideration and $n$ is the number of variables. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under our assumptions, it is the first roadmap algorithm with output size and running time polynomial in ${\left(nD\right)}^{nlog\left(d\right)}$.

Determinantal sets, singularities and application to optimal control in medical imagery

Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures. Geometric optimal control leads us here to analyze mero-morphic vector fields depending upon physical parameters, and having their singularities defined by a determinantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in some prescribed semi-algebraic set. In [24], we develop a dedicated algorithm for real root classification of the singularities of the rank defects of a polynomial matrix, cut with a given semi-algebraic set. The algorithm works under some genericity assumptions which are easy to check. These assumptions are not so restrictive and are satisfied in the aforementioned application. As more general strategies for real root classification do, our algorithm needs to compute the critical loci of some maps, intersections with the boundary of the semi-algebraic domain, etc. In order to compute these objects, the determinantal structure is exploited through a stratification by the rank of the polynomial matrix. This speeds up the computations by a factor 100. Furthermore, our implementation is able to solve the application in medical imagery, which was out of reach of more general algorithms for real root classification. For instance, computational results show that the contrast problem where one of the matters is water is partitioned into three distinct classes.

Optimal Control of an Ensemble of Bloch Equations with Applications in MRI

The optimal control of an ensemble of Bloch equations describing the evolution of an ensemble of spins is the mathematical model used in Nuclear Resonance Imaging and the associated costs lead to consider Mayer optimal control problems. The Maximum Principle allows to parameterize the optimal control and the dynamics is analyzed in the framework of geometric optimal control. This leads to numerical implementations or suboptimal controls using averaging principle as presented in [25].

Critical Point Computations on Smooth Varieties: Degree and Complexity bounds

Let $V\subset {ℂ}^n$ be an equidimensional algebraic set and $g$ be an $n$-variate polynomial with rational coefficients. Computing the critical points of the map that evaluates $g$ at the points of $V$ is a cornerstone of several algorithms in real algebraic geometry and optimization. Under the assumption that the critical locus is finite and that the projective closure of $V$ is smooth, we provide in [31] sharp upper bounds on the degree of the critical locus which depend only on $deg\left(g\right)$ and the degrees of the generic polar varieties associated to $V$. Hence, in some special cases where the degrees of the generic polar varieties do not reach the worst-case bounds, this implies that the number of critical points of the evaluation map of $g$ is less than the currently known degree bounds. We show that, given a lifting fiber of $V$, a slight variant of an algorithm due to Bank, Giusti, Heintz, Lecerf, Matera and Solernó computes these critical points in time which is quadratic in this bound up to logarithmic factors, linear in the complexity of evaluating the input system and polynomial in the number of variables and the maximum degree of the input polynomials.